1638E - Colorful Operations - CodeForces Solution

#include <bits/stdc++.h>
typedef long long ll;
const int BUFFER = 1 << 18;
struct ostream
{
    char buffer[BUFFER], *pos = buffer, *end = buffer + BUFFER;
    ~ostream() { flush(); }
    void flush() { fwrite(buffer, 1, pos - buffer, stdout), pos = buffer; }
    void put(char ch)
    {
        if (pos == end)
            flush();
        *(pos++) = ch;
    }
    template <typename V>
    void put(V num)
    {
        if (num)
            put(num / 10), put((char)(num % 10 + '0'));
    }
    template <typename V>
    void putNum(V num)
    {
        if (num < 0)
            put('-'), put(-num);
        else if (num == 0)
            put('0');
        else
            put(num);
    }
    ostream &operator<<(char s) { return put(s), *this; }
    ostream &operator<<(const char *s)
    {
        while (*s)
            put(*(s++));
        return *this;
    }
    ostream &operator<<(int num) { return putNum(num), *this; }
    ostream &operator<<(unsigned num) { return putNum(num), *this; }
    ostream &operator<<(ll num) { return putNum(num), *this; }
} cout;
struct istream
{
    char buffer[BUFFER], *pos = buffer, *end = buffer;
    int get()
    {
        if (pos == end)
        {
            end = buffer + fread(buffer, 1, BUFFER, stdin), pos = buffer;
            if (pos == end)
                return 0;
        }
        return *(pos++);
    }
    template <typename V>
    void getNum(V &num)
    {
        int sign = 0, ch, done = 0;
        num = 0;
        while (ch = get())
            if (ch == '-')
                sign = 1;
            else if ('-' < ch)
                num = 10 * num + ch - '0', done = 1;
            else if (done)
                break;
        if (sign)
            num = -num;
    }
    istream &operator>>(char &ch)
    {
        while ((ch = get()) <= ' ')
            ;
        return *this;
    }
    istream &operator>>(int &num) { return getNum(num), *this; }
    istream &operator>>(unsigned &num) { return getNum(num), *this; }
    istream &operator>>(ll &num) { return getNum(num), *this; }
} cin;
#ifdef LOCAL
#include "debug.h"
#else
#define log(...) 9
#endif

template <typename V, int maxN>
struct fenwick
{
    V nums[maxN];
    int n;
    void clear(int n) { this->n = n, memset(nums, 0, sizeof(V) * n); }
    void add(int i, V value)
    {
        for (; i < n; i |= i + 1)
            nums[i] += value;
    }
    V query(int i)
    {
        V ans = 0;
        for (; 0 <= i; i = (i & (i + 1)) - 1)
            ans += nums[i];
        return ans;
    }
};
fenwick<ll, 1'000'000> f;

void testCase()
{
    int n, q;
    cin >> n >> q;

    ll total[n];
    std::map<int, int> colors;
    memset(total, 0, sizeof(total));
    colors[n] = 0;
    f.clear(n);

    while (q--)
    {
        char ch = cin.get();
        while (cin.get() != ' ')
            ;

        if (ch == 'C')
        {
            int l, r, c;
            cin >> l >> r >> c;
            l--, c--;

            auto current = colors.lower_bound(l);

            if (current->first == l)
                current++;
            else
                colors[l] = current->second;

            while (current->first < r)
            {
                f.add(l, total[current->second] - total[c]), l = current->first;
                f.add(l, total[c] - total[current->second]);

                if ((current = colors.erase(current)) == colors.end())
                    break;
            }

            if (l < r)
            {
                f.add(l, total[current->second] - total[c]);
                f.add(r, total[c] - total[current->second]);
            }

            colors[r] = c;
        }
        else if (ch == 'A')
        {
            int c, x;
            cin >> c >> x;
            total[c - 1] += x;
        }
        else
        {
            int i;
            cin >> i;
            cout << f.query(i - 1) + total[colors.upper_bound(i - 1)->second] << '\n';
        }
    }
}

int main()
{
    testCase();
    return 0;
}